Search results for "Cylindrical algebraic decomposition"
showing 5 items of 5 documents
Exacus: Efficient and Exact Algorithms for Curves and Surfaces
2005
We present the first release of the Exacus C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.
A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES
1992
In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.
Two-view “cylindrical decomposition” of binary images
2001
This paper describes the discrete cylindrical algebraic decomposition (DCAD) construction along two orthogonal views of binary images. The combination of two information is used to avoid ambiguities for image recognition purposes. This algorithm associates an object connectivity graph to each connected component, allowing a complete description of the structuring information. Moreover, an easy and compact representation of the scene is achieved by using strings in a five letter alphabet. Examples on complex digital images are also provided. © 2001 Elsevier Science Inc.
Representing 2D Digital Objects
2000
The paper describes the combination a multi-views approach to represent connected components of 2D binary images. The approach is based on the Object Connectivity Graph (OCG), which is a sub-graph of the connectivity graph generated by the Discrete Cylindrical Algebraic Decomposition(DCAD) performed in the 2D discrete space. This construction allows us to find the number of connected components, to determine their connectivity degree, and to solve visibility problem. We show that the CAD construction, when performed on two orthogonal views, supply information to avoid ambiguities in the interpretation of each image component. The implementation of the algorithm is outlined and the computati…